home *** CD-ROM | disk | FTP | other *** search
/ Group 42-Sells Out! - The Information Archive / Group 42 Sells Out (Group 42) (1996).iso / crypto / polygona.txt < prev    next >
Text File  |  1995-11-30  |  8KB  |  161 lines
  1.  
  2.             THE CRYPTOGRAPHIC USES OF POLYGONAL SEQUENCES
  3.  
  4.                          By C. David Colston
  5. INTRODUCTION
  6.  
  7.      Polygonal sequences are a series of numbers that are generated by
  8. offset addition to the previous members of the sequence. The lowest
  9. order of these sequences (other than sequence zero or 1, 2, 3, 4 ,5...
  10. etc.) is the triangular sequence. It is created by taking the starting
  11. number 1 and offset of 1, constantly adding 1 to the offset, and
  12. summing the result. 1 + 2 + 3 + 4... are added, resulting in the
  13. numbers 1, 3, 6, 10...
  14.  
  15.      The next sequence is the square sequence in which offset is
  16. increase by two each time, 1 + 3 + 5 + 7...  This results in the
  17. numbers 1, 4, 9, 16... The third sequence (a pentagon) increases the
  18. offset by three each time 1 + 4 + 7 + 10 ... and it results in the
  19. numbers 1, 5, 12, 22... These sequences are called polygonal because
  20. the resulting numbers can be ordered into rigid geometric shapes.
  21.  
  22.                               Examples:
  23.  
  24.       1                         1  4  9 16
  25.     2   3       (Triangle)      2  3  8 15  (Square)
  26.   4   5   6                     5  6  7 14
  27. 7   8   9   10                 10 11 12 13
  28.  
  29.  
  30. CALCULATION OF POLYGONAL NUMBERS
  31.  
  32.      Because offset counting and addition is a cumbersome process it
  33. is helpful to note that any member (M) of a given polygonal sequence
  34. (PS) may be calculated by the following formula:
  35.  
  36.     (M X M + M)/2 + (PS-1) X ((M-1) X (M-1) + (M-1))/2
  37.  
  38. It is also helpful to note that (PS + 2) is the number of sides in the
  39. resulting polygonal sequence.
  40.  
  41. The formula resolves as follows for the first four sequences:
  42.  
  43. Triangle:  (M X M + M)/2
  44. Square:    M X M
  45. Pentagon:  (3 X M X M - M)/2
  46. Hexagon:   2 X M X M - M
  47.  
  48. THE MODULAR RESIDUE OF POLYGONAL NUMBERS
  49.  
  50.      Polygonal sequences have ordered properties modulo a prime
  51. number. On the next page is a complete set of the modular residue of
  52. the first 23 polygonal sequences modulo the prime 23. The horizontal
  53. columns are, from left to right, the sequence members from 1 to 23.
  54. The rows from top to bottom are the polygonal sequences from 1 to 23
  55. and are numbered from 1 to 23 accordingly.
  56.  
  57.                     
  58. ______________________________________________________________________
  59.  
  60.                             Page 2
  61.  
  62. PS#|
  63. ---+------------------------------------------------------------------
  64.  1 |1| 3| 6|10|15|21| 5|13|22| 9|20| 9|22|13| 5|21|15|10| 6| 3| 1| 0|0
  65. ---+-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
  66.  2 |1| 4| 9|16| 2|13| 3|18|12| 8| 6| 6| 8|12|18| 3|13| 2|16| 9| 4| 1|0
  67. ---+-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
  68.  3 |1| 5|12|22|12| 5| 1| 0| 2| 7|15| 3|17|11| 8| 8|11|17| 3|15| 7| 2|0
  69. ---+-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
  70.  4 |1| 6|15| 5|22|20|22| 5|15| 6| 1| 0| 3|10|21|13| 9| 9|13|21|10| 3|0
  71. ---+-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
  72.  5 |1| 7|18|11| 9|12|20|10| 5| 5|10|20|12| 9|11|18| 7| 1| 0| 4|13| 4|0
  73. ---+-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
  74.  6 |1| 8|21|17|19| 4|18|15|18| 4|19|17|21| 8| 1| 0| 5|16|10|10|16| 5|0
  75. ---+-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
  76.  7 |1| 9| 1| 0| 6|19|16|20| 8| 3| 5|14| 7| 7|14| 5| 3| 8|20|16|19| 6|0
  77. ---+-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
  78.  8 |1|10| 4| 6|16|11|14| 2|21| 2|14|11|16| 6| 4|10| 1| 0| 7|22|22| 7|0
  79. ---+-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
  80.  9 |1|11| 7|12| 3| 3|12| 7|11| 1| 0| 8| 2| 5|17|15|22|15|17| 5| 2| 8|0
  81. ---+-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
  82. 10 |1|12|10|18|13|18|10|12| 1| 0| 9| 5|11| 4| 7|20|20| 7| 4|11| 5| 9|0
  83. ---+-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
  84. 11 |1|13|13| 1| 0|10| 8|17|14|22|18| 2|20| 3|20| 2|18|22|14|17| 8|10|0
  85. ---+-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
  86. 12 |1|14|16| 7|10| 2| 6|22| 4|21| 4|22| 6| 2|10| 7|16|14| 1| 0|11|11|0
  87. ---+-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
  88. 13 |1|15|19|13|20|17| 4| 4|17|20|13|19|15| 1| 0|12|14| 6|11| 6|14|12|0
  89. ---+-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
  90. 14 |1|16|22|19| 7| 9| 2| 9| 7|19|22|16| 1| 0|13|17|12|21|21|12|17|13|0
  91. ---+-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
  92. 15 |1|17| 2| 2|17| 1| 0|14|20|18| 8|13|10|22| 3|22|10|13| 8|18|20|14|0
  93. ---+-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
  94. 16 |1|18| 5| 8| 4|16|21|19|10|17|17|10|19|21|16| 4| 8| 5|18| 1| 0|15|0
  95. ---+-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
  96. 17 |1|19| 8|14|14| 8|19| 1| 0|16| 3| 7| 5|20| 6| 9| 6|20| 5| 7| 3|16|0
  97. ---+-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
  98. 18 |1|20|11|20| 1| 0|17| 6|13|15|12| 4|14|19|19|14| 4|12|15|13| 6|17|0
  99. ---+-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
  100. 19 |1|21|14| 3|11|15|15|11| 3|14|21| 1| 0|18| 9|19| 2| 4| 2|19| 9|18|0
  101. ---+-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
  102. 20 |1|22|17| 9|21| 7|13|16|16|13| 7|21| 9|17|22| 1| 0|19|12| 2|12|19|0
  103. ---+-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
  104. 21 |1| 0|20|15| 8|22|11|21| 6|12|16|18|18|16|12| 6|21|11|22| 8|15|20|0
  105. ---+-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
  106. 22 |1| 1| 0|21|18|14| 9| 3|19|11| 2|15| 4|15| 2|11|19| 3| 9|14|18|21|0
  107. ---+-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
  108. 23 |1| 2| 3| 4| 5| 6| 7| 8| 9|10|11|12|13|14|15|16|17|18|19|20|21|22|0
  109. ----------------------------------------------------------------------
  110.  
  111. USING MODULAR RESIDUE TO MAKE A PUBLIC KEY
  112.  
  113. The cryptographic implications can be easily seen. For example, any
  114. member of the first polygonal sequence can be transform to be a member
  115. the second sequence and used for a public key:
  116. _____________________________________________________________________
  117.  
  118.                               Page 3
  119.  
  120. p = prime 1
  121. q = prime 2
  122. N= p X q
  123. M= message
  124. C = Cipher_text
  125.  
  126. Encrypt (using polygonal sequence 1): (Sender knows N by not p and q.)
  127.  
  128.  (M X M + M)/2 modulo N == C  (The resolution of the formula for
  129. polygonal sequence 1.)
  130.  
  131. Decrypt: (Receiver knows p and q.)
  132.  
  133. (C X 8 + 1) modulo N == ((M X 2 + 1) X  (M X 2 + 1)) modulo N
  134.  
  135. This converts the triangular encryption into a member of the square
  136. sequence and allows for solution. Solve for (M X 2 + 1) modulo p and
  137. (M X 2 + 1) modulo q. Using Chinese remainder theory the results may
  138. be used to produce four possible solutions. 1 is subtracted from the
  139. four possible results and the results are divided by 2. Many methods
  140. can be used to avoid ambiguity, but presumably only one of the four
  141. possible M's will make sense.
  142.  
  143.      A similar possibility exists for the use of the fourth or hexagon
  144. sequence, because it may also be changed into a member of the square
  145. sequence by (C X 8 = 1), but decryption is more complicated. The
  146. resulting squares require the subtraction of 1 and division by 2 AND
  147. THEN the additional step of adding 1 and the dividing by 2.
  148.  
  149.      For conventional key purposes it should also be noted that the
  150. vertical columns in the example contain all numbers from 0 to (N-1)
  151. (the exception are the 1 column and the N column which are all 1 or 0)
  152. and can be readily determined by their additive quality modulo N,
  153. as suggested by the general formula.
  154.  
  155.      To the best my knowledge, O. Joel Benston and myself are the
  156. originators of the idea of using polygonal sequences (other than the
  157. square sequence) for cryptographic purposes. We are considering
  158. patenting the idea. If you have knowledge of other persons, who have
  159. suggested a similar approach, please advise us. (501) 484-5489
  160.  
  161.